/*
 * 版权所有 (C) 2015 知启蒙(ZHIQIM) 保留所有权利。[欢迎加盟知启蒙，一起邂逅框架梦]
 * 
 * https://www.zhiqim.com/gitcan/zhiqim/zhiqim_account.htm
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.zhiqim.account.util;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class WordUtil
{

    /**
     * 统计字符个数
     * @param str
     * @return
     */
    public static HashMap<Character, Integer> count(String str)
    {
        char[] chars = str.toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();

        for (char c : chars)
        {
            if (!map.containsKey(c))
            {
                map.put(c, 1);
            }
            else
            {
                map.put(c, map.get(c) + 1);
            }
        }

        return map;
    }

    /**
     * 余弦相似度计算
     * @param s1
     * @param s2
     * @return
     */
    public static double cosine(String s1, String s2)
    {
        Set<Character> set = new HashSet<>();

        char[] chars1 = s1.toCharArray();
        for (char c : chars1)
        {
            set.add(c);
        }

        char[] chars2 = s2.toCharArray();
        for (char c : chars2)
        {
            set.add(c);
        }

        int[] v1 = new int[set.size()];
        int[] v2 = new int[set.size()];
        HashMap<Character, Integer> map1 = count(s1);
        HashMap<Character, Integer> map2 = count(s2);
        
        int index = 0;
        for (char ch : set)
        {
            v1[index] = map1.containsKey(ch) ? map1.get(ch) : 0;
            v2[index] = map2.containsKey(ch) ? map2.get(ch) : 0;
            index ++;
        }
        
        double similarity = 0, sum = 0, sum1 = 0, sum2 = 0;
        for (int i=0; i<set.size(); i++)
        {
            sum += v1[i]*v2[i];
            sum1 += v1[i]*v1[i];
            sum2 += v2[i]*v2[i];
        }
        
        similarity = sum / (Math.sqrt(sum1) * Math.sqrt(sum2));
        return similarity;
    }
    
    /**
     * Levenshtein Distance (Edit Distance) 算法，是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数
     * @param s1
     * @param s2
     * @return
     */
    public static double editDistance(String s1, String s2)
    {
        int m = s1.length(), n = s2.length();
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        
        int[][] matrix = new int[m+1][n+1];
        
        for (int i=0; i<m+1; i++)
        {
            matrix[i][0] = i;
        }
        
        for (int i=0; i<n+1; i++)
        {
            matrix[0][i] = i;
        }

        for (int j=1; j<m+1; j++)
        {
            for (int k=1; k<n+1; k++)
            {
                int w = chars1[j-1] == chars2[k-1] ? 0 : 1;
                int x = Math.min(matrix[j-1][k]+1, matrix[j][k-1]+1);
                matrix[j][k] = Math.min(x, matrix[j-1][k-1]+w);
            }
        }
        
        int dis = matrix[m][n];
        double similarity = 1 - ((double)dis / Math.max(m, n));
        
        return similarity;
    }
}
